// 快速排序
// function quickSort(arr) {
//   if(arr.length <= 1) return arr          //递归终止条件
//   const pivot = arr.length / 2 | 0        //基准点
//   const pivotValue = arr.splice(pivot, 1)
//   const leftArr = []
//   const rightArr = []
//   arr.forEach(val => {
//       val > pivotValue ? rightArr.push(val) : leftArr.push(val)
//   })
//   return [ ...quickSort(leftArr), pivotValue, ...quickSort(rightArr)]
// }

// 单路快速排序
// function quickSort(arr, left = 0, right = arr.length - 1) {          //这个left和right代表分区后“新数组”的区间下标，因为这里没有新开数组，所以需要left/right来确认新数组的位置
//   if (left < right) {
//       let pos = left - 1                      //pos即“被置换的位置”，第一趟为-1
//       for(let i = left; i <= right; i++) {    //循环遍历数组，置换元素
//           let pivot = arr[right]              //选取数组最后一位作为基准数，
//           if(arr[i] <= pivot) {               //若小于等于基准数，pos++，并置换元素, 这里使用小于等于而不是小于, 其实是为了避免因为重复数据而进入死循环
//               pos++
//               let temp = arr[pos]
//               arr[pos] = arr[i]
//               arr[i] = temp
//           }
//       }
//       //一趟排序完成后，pos位置即基准数的位置，以pos的位置分割数组
//       quickSort(arr, left, pos - 1)        
//       quickSort(arr, pos + 1, right)
//   }
//   return arr      //数组只包含1或0个元素时(即left>=right)，递归终止
// }

function partition(arr, left, right) {
  var pivot = arr[Math.floor((right + left) / 2)]
  while(left <= right) {
    while(arr[left] < pivot) {
      left++
    }
    while(arr[right] > pivot) {
      right--
    }
    if(left <= right) {
      var tmp = arr[left]
      arr[left] = arr[right]
      arr[right] = tmp
      left++
      right--
    }
  }
  return left
}
// 双指针快速排序
// function quickSort(arr, left = 0, right = arr.length - 1) {
//   var index;
//   if (arr.length > 1) {
//     index = partition(arr, left, right)
//     if(left < index - 1) {
//       quickSort(arr, left, index - 1)
//     }
//     if(index< right) {
//       quickSort(arr, index - 1, right)
//     }
//   }
//   return arr      //数组只包含1或0个元素时(即left>=right)，递归终止  
// }

// 三路快速排序
function quickSort(arr, left = 0, right = arr.length - 1) {          //这个left和right代表分区后“新数组”的区间下标，因为这里没有新开数组，所以需要left/right来确认新数组的位置
  if (left < right) {
      let pos1 = left - 1                      //pos即“被置换的位置”，第一趟为-1
      let pos2 = pos1
      for(let i = left; i <= right; i++) {    //循环遍历数组，置换元素
          let pivot = arr[right]              //选取数组最后一位作为基准数，
          if(arr[i] < pivot) {               //若小于等于基准数，pos++，并置换元素, 这里使用小于等于而不是小于, 其实是为了避免因为重复数据而进入死循环
            pos1++
            pos2++
            let temp = arr[pos2]
            arr[pos2] = arr[pos1]
            arr[pos1] = arr[i]
            arr[i] = temp
          } else if (arr[i] === pivot) {
            pos2++
            let temp = arr[pos2]
            arr[pos2] = arr[i]
            arr[i] = temp
          }
      }
      //一趟排序完成后，pos位置即基准数的位置，以pos的位置分割数组
      quickSort(arr, left, pos1 - 1)        
      quickSort(arr, pos2 + 1, right)
  }
  return arr      //数组只包含1或0个元素时(即left>=right)，递归终止
}

const arr = []
for(let i = 0; i < 10000000; i++) {
  arr.push(Math.random() * 100000)
}

const start = new Date()
quickSort(arr)
const end = new Date()
console.log(end - start)
// console.log(93240)
// console.log(2034)
// console.log(2151)

